package jm.algorithm.sort;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description 桶排序
 * @date 2022/5/8 20:58
 */
public class BucketSort {

    public static void main(String[] args) {
        Double[] arr = {0.34, 0.47, 0.29, 0.84, 0.45, 0.38, 0.35, 0.76};
        bucketSort(arr);
        for (Double aDouble : arr) {
            System.out.print(aDouble + "_");
        }
    }

    public static void bucketSort(Double[] arr){
        // 创建一个存放 double类型的list 的数组
        List<Double>[] buckets = new List[arr.length];
        // 遍历数组
        for (Double info : arr) {
            // 根据长度计算索引
            int bucketIndex = (int) (info * arr.length);
            // 将当前索引位置的数组赋值给list
            List<Double> bucket = buckets[bucketIndex];
            // 如果list为空，新建一个
            if (bucket == null){
                bucket = new LinkedList<>();
                buckets[bucketIndex] = bucket;
            }
            // 将当前值存放到索引位置的链表中
            bucket.add(info);
        }

        // 对每个桶进行排序
        int index = 0;
        // 遍历桶数组
        for (List<Double> bucket : buckets) {
            // 如果桶数组为空，不进行操作
            if (bucket == null) continue;
            // 调用JDK方法对当前桶进行排序
            bucket.sort(null);
            // 遍历当前桶，赋值给原先的序列
            for (Double aDouble : bucket) {
                arr[index++] = aDouble;
            }
        }
    }
}
